import {cbtPrint} from 'hy-algokit'
interface IHeap<T> {
  data: T[]; // 存储数据
  size: number; // 大小
  insert(value: T): void; // 插入
  extract(): T | undefined; // 抛出最值
  peek(): T | undefined; // 获取最值
  isEmpty(): boolean; // 判空
  build_heap(array: T[]): void; // 构建堆
}

class Heap<T = number> implements IHeap<T> {
  data: T[] = [];
  size: number = 0;

  // 私有工具方法
  private swap(i: number, j: number) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }
  // 寻找父节点
  private getParentIndex(index: number): number {
    return Math.floor(index / 2 - 1);
  }
  // 寻找左节点
  private getLeftIndex(index: number): number {
    return 2 * index + 1;
  }
  // 寻找子节点
  private getRightIndex(index: number): number {
    return 2 * index + 2;
  }
  // 上滤节点，跟父节点比较，大于就换位置
  private heapify_up(index: number) {
    const parentIndex = this.getParentIndex(index);
    if (parentIndex < 0) {
      // 超出定点退出
      return;
    }
    const data1 = this.data[index];
    const data2 = this.data[parentIndex];
    if (data1 <= data2) {
      // 父节点小于子节点
      return;
    }
    if (data1 > data2) {
      // 父节点大于子节点, 换元素后继续上滤
      this.swap(index, parentIndex);
      this.heapify_up(parentIndex);
    }
  }
  // 下滤节点，跟大的子节点比较，小于就换位置
  private heapify_down(index: number) {
    const current = this.data[index];
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    let contrastIndex: number = 0;
    if (this.data[leftIndex] === undefined) {
      return;
    } else if (this.data[rightIndex] === undefined) {
      contrastIndex = leftIndex;
    } else {
      contrastIndex = this.data[leftIndex]! > this.data[rightIndex]! ? leftIndex : rightIndex;
    }

    if (current >= this.data[contrastIndex]) {
      return;
    } else {
      this.swap(index, contrastIndex);
      this.heapify_down(contrastIndex);
    }
  }

  insert(value: T) {
    this.data.push(value);
    this.size++;
    if (this.size === 1) return;
    // 开始上滤
    this.heapify_up(this.size - 1);
  }
  extract(): T | undefined {
    if (this.size === 0) {
      return undefined;
    } else if (this.size < 2) {
      this.size--;
      return this.data.pop()!;
    } else {
      const current = this.data.pop()!;
      this.data[0] = current;
      this.size--;
      // 开始下滤
      this.heapify_down(0);
      return current;
    }
  }
  peek(): T | undefined {
    return this.data[0];
  }
  isEmpty(): boolean {
    return this.size === 0;
  }
  build_heap(array: T[]) {
    this.data = array;
    const length = this.getParentIndex(array.length - 1);
    for (let i = length; i >= 0; i--) {
        // 循环所有的非子节点，从最后一个非子节点开始，开始下滤
        this.heapify_down(i);
    }
  }
  print() {
    cbtPrint(this.data);
  }
}

const heap = new Heap<number>();

heap;
heap.insert(100);
heap.insert(19);
heap.insert(36);
heap.insert(17);
heap.insert(3);
heap.insert(25);
heap.insert(1);
heap.insert(2);
heap.insert(7);
heap.print()

heap.insert(133);
heap.print()

heap.extract();
heap.print()


heap.build_heap([9,11,20,5,23,45])
heap.print()
